class Solution {
    public:
        int is_existent[7][7] = {0};
    
        bool exist(vector<vector<char>>& board, string word) {
            int n = board.size(),m=board[0].size();
            for(int i = 0 ; i < n ; i++){
                for(int j = 0 ; j < m ; j++){
                    if(board[i][j] == word[0]){
                        is_existent[i][j] = 1;
                        if(dfs(board,word,i,j,1))   return true;
                        is_existent[i][j] = 0;
                    }
                }
            }
            return false;
        }
        int indexx[4] = {-1,1,0,0};
        int indexy[4] = {0,0,1,-1};
        bool dfs(vector<vector<char>>& board, string word,int i,int j ,int pos){
            int n = board.size(),m=board[0].size();
            if(pos == word.size()){
                return true;
            }
            for(int k = 0 ; k < 4; k++){
                int x = indexx[k]+i;
                int y = indexy[k]+j;
                if( x>=0 && x<n && y>=0 && y <m&&is_existent[x][y] == 0  && board[x][y] == word[pos]){
                    is_existent[x][y] = 1;
                    if(dfs(board,word,x,y,pos+1)) return true;
                    is_existent[x][y] = 0;
                }
            }
            return false;
        }
    };